package com.leetcode;

import java.util.ArrayList;

/**
 * 2002. 两个回文子序列长度的最大乘积
 *
 * @author yml
 * 给你一个字符串s，请你找到s中两个不相交回文子序列，使得它们长度的乘积最大。两个子序列在原字符串中如果没有任何相同下标的字符，则它们是不相交的。
 * <p>
 * 请你返回两个回文子序列长度可以达到的最大乘积。
 * <p>
 * 子序列指的是从原字符串中删除若干个字符（可以一个也不删除）后，剩余字符不改变顺序而得到的结果。如果一个字符串从前往后读和从后往前读一模一样，那么这个字符串是一个 回文字符串。
 * <p>
 * 来源：力扣（LeetCode）
 * 链接：https://leetcode-cn.com/problems/maximum-product-of-the-length-of-two-palindromic-subsequences
 * 著作权归领扣网络所有。商业转载请联系官方授权，非商业转载请注明出处。
 */
public class LeetCode2002 {


    public static int maxProduct(String s) {
        int len = s.length();
        int m = 1 << len;
        char[] cArr = s.toCharArray();
        ArrayList<int[]> record = new ArrayList<>();

        for (int i = 0; i < m; i++) {
            if (check(cArr, i)) {
                record.add(new int[]{i, Integer.bitCount(i)});
            }
        }

        int[][] recordArr = record.toArray(new int[0][0]);
        int res = 0;
        if (recordArr.length >= 2) {
            for (int i = 0; i < recordArr.length - 1; i++) {
                int x = recordArr[i][0];
                int len_x = recordArr[i][1];
                for (int j = i + 1; j < recordArr.length; j++) {
                    int y = recordArr[j][0];
                    int len_y = recordArr[j][1];
                    if ((x & y) == 0) {
                        res = Math.max(res, len_x * len_y);
                    }
                }
            }
        }

        return res;
    }


    /**
     * 检测该状态压缩编号所对应的字符串是否是回文串
     *
     * @param s     整个字符串对应的char数组
     * @param state 状态压缩编号
     * @return 是否是回文串
     */
    private static boolean check(char[] s, int state) {
        int left = 0, right = s.length - 1;

        // 检查 state 对应的子序列是不是回文串
        while (left < right) {
            // 将 left 和 right 对应上 「状态所对应的字符」 位置
            while (left < right && (state >> left & 1) == 0) {
                left++;
            }
            while (left < right && (state >> right & 1) == 0) {
                right--;
            }
            if (s[left] != s[right]) {
                return false;
            }
            left++;
            right--;
        }

        return true;
    }

}
